package br.quest.math;

import java.util.ArrayList;
import java.util.List;
import static java.lang.Math.*;
import android.location.Location;
import br.quest.Config;
import br.quest.gps.GpsUtils;
import br.quest.models.Waypoint;

/**
 * The goal of this algorithm is to compress a GPS Route, basically excluding redundant points, such as a group of
 * points in a straight line. There is of course a loss of precision, that can be controlled modifing the
 * mathRamerEpsilon configuration.
 * 
 * @author Rodrigo
 * 
 */
public class RamerDouglasPeucker {

	/**
	 * Compress a set of waypoints, removing redundant points.
	 * 
	 * @param waypoints The route to be compressed
	 * @return The compressed route, with a small loss of precision.
	 */
	public static List<Waypoint> compressWaypoints(List<Waypoint> waypoints) {
		return ramerDouglasPeucker(waypoints, 0, waypoints.size());
	}

	private static List<Waypoint> ramerDouglasPeucker(List<Waypoint> points, int startIndex, int endIndex) {
		int maxDistIndex = findMaxPerpDistPoint(points, startIndex, endIndex);
		if (maxDistIndex > 0) {
			List<Waypoint> result1 = ramerDouglasPeucker(points, startIndex, maxDistIndex);
			List<Waypoint> result2 = ramerDouglasPeucker(points, maxDistIndex, endIndex);
			result1.addAll(result2);
			return result1;

		} else {
			List<Waypoint> result = new ArrayList<Waypoint>();
			result.add(points.get(startIndex));
			result.add(points.get(endIndex));
			return result;
		}
	}

	/**
	 * Finds the point with greatest perpendicular distance from any straight line from the Waypoint list points.
	 * 
	 * @param points
	 * @param startIndex
	 * @param endIndex
	 * @return An integer specifing the list index of the found point or -1 if the maximun distance is smaller than the
	 *         configured epsilon, in meters.
	 */
	private static int findMaxPerpDistPoint(List<Waypoint> points, int startIndex, int endIndex) {
		double maxDistance = 0D;
		int index = 0;
		Location p1 = points.get(startIndex).getCoord();
		Location p2 = points.get(endIndex).getCoord();
		double xDelta = abs(p2.getLongitude() - p1.getLongitude());
		double yDelta = abs(p2.getLatitude() - p1.getLatitude());
		if ((xDelta == 0) && (yDelta == 0)) {
			return -1;
		}
		for (int i = startIndex + 1; i < endIndex; i++) {
			Location p3 = points.get(i).getCoord();
			final double u =
					((p3.getLongitude() - p1.getLongitude()) * xDelta + (p3.getLatitude() - p1.getLatitude()) * yDelta)
							/ (xDelta * xDelta + yDelta * yDelta);
			final Location closestPoint;
			if (u < 0)
				closestPoint = p1;
			else if (u > 1)
				closestPoint = p2;
			else {
				closestPoint = new Location("gps");
				closestPoint.setLongitude(p1.getLongitude() + u * xDelta);
				closestPoint.setLatitude(p1.getLatitude() + u * yDelta);
			}
			double distance = GpsUtils.distance(closestPoint, p3);
			if (distance > maxDistance) {
				maxDistance = distance;
				index = i;
			}
		}
		if (maxDistance > Config.getMathRamerEpsilon()) {
			return index;
		}
		return -1;
	}
}
